#include<stdlib.h>
#include<string.h>

#include"set.h"

set_node_t *newsetnode()
{
   set_node_t *nnode = malloc(sizeof(set_node_t));
   nnode->left = nnode->right = nnode->data = NULL;
   return nnode;
}

set_t *newSet(int (*compare)(const void *, const void *))
{
   set_t *ret = malloc(sizeof(set_t));
   ret->size = 0;
   ret->root = NULL;
   ret->compare = compare;
   return ret;
}

void ssetClear(set_node_t **n)
{
   if((*n)->left != NULL)
      ssetClear(&((*n)->left));
   if((*n)->right != NULL)
      ssetClear(&((*n)->right));
   free(*n);
   *n = NULL;
}

void setClear(set_t *set)
{
   if(set == NULL)
      return;
   else if(set->root != NULL)
      ssetClear(&(set->root));
   set->size = 0;
}

int ssetPut(set_node_t **n, void *object,
   int(*compare)(const void *, const void *))
{
   if (*n == NULL)
   {
      *n = newsetnode();
      (*n)->data = object;
      return 1;
   }
   else
   {
      int c = compare(object, (*n)->data);
      if (c < 0)
         return ssetPut(&((*n)->left), object, compare);
      else if (c > 0)
         return ssetPut(&((*n)->right), object, compare);
      else
      {
         (*n)->data = object;
         return 0;
      }
   }
}

void setPut(set_t *set, void *object)
{
   set->size += ssetPut(&(set->root), object, set->compare);
}

int ssetContains(set_node_t *n, void *object,
   int (*compare) (const void *, const void *))
{
   if (n == NULL)
      return 0;
   else
   {
      int c = compare(object, n->data);
      if (c < 0)
         return ssetContains(n->left, object, compare);
      else if (c > 0)
         return ssetContains(n->right, object, compare);
      else
         return 1;
   }
}

int setContains(set_t *set, void *object)
{
   return ssetContains(set->root, object, set->compare);
}

set_node_t **ssetfindNode(set_node_t **r, void *object,
   int (*compare) (const void *, const void *))
{
   set_node_t **ret = NULL;
   if (r != NULL && *r != NULL)
   {
      int c = compare(object, (*r)->data);
      if(c < 0)
         ret = ssetfindNode(&((*r)->left), object, compare);
      else if (c > 0)
         ret = ssetfindNode(&((*r)->right), object, compare);
      else
         ret = r;
   }
   return ret;
}

int ssetRemove(set_node_t **n, void *object,
   int (*compare) (const void *, const void *))
{
   set_node_t **f;
   if((f = ssetfindNode(n, object, compare)) == NULL)
      return 0;
   int l = (*f)->left == NULL;
   int r = (*f)->right == NULL;

   // Delete f
   // Leaf case
   if(l && r)
   {
      free(*f);
      *f = NULL;
   } // Right child
   else if(l)
   {
      set_node_t *fill = (*f)->right;
      free(*f);
      *f = fill;
   } // Left child
   else if(r)
   {
      set_node_t *fill = (*f)->left;
      free(*f);
      *f = fill;
   } // Double child
   else
   {  // Get leftmost child of right child
      set_node_t **fill = &((*f)->right);
      while((*fill)->left != NULL)
         fill = &((*fill)->left);
      // Swap the info in the node to delete and fill
      (*f)->data = (*fill)->data;
      // Delete fill instead
      free(*fill);
      *fill = NULL;
   }
   return 1;
}

void setRemove(set_t *set, void *object)
{
   if(set == NULL || set->root == NULL)
      return;
   if(ssetRemove(&(set->root), object, set->compare))
      set->size--;
}

int  setIsEmpty(set_t *set)
{
   return set->size == 0;
}
